class Solution {
    vector<vector<string>> result;
    vector<string> path;

    bool isPalindrome(const string& s, int begin, int end)
    {
        while (begin <= end)
        {
            if (s[begin] != s[end]) return false;
            ++begin;
            --end;
        }
        return true;
    }
    void backTracking(const string& s, int startIndex)
    {
        if (startIndex >= s.size())
        {
            result.push_back(path);
            return;
        }
        for (int i = startIndex; i < s.size(); ++i)
        {
            if (isPalindrome(s, startIndex, i)) path.push_back(s.substr(startIndex, i - startIndex + 1));
            else continue;

            backTracking(s, i + 1);
            path.pop_back();
        }
    }
public:
    vector<vector<string>> partition(string s) {
        backTracking(s, 0);
        return result;
    }
};